package com.qch.edu.sort.jiandanSort;

/**
 * @Author qch
 * @Date 2021/3/6
 * 选择排序：不稳，O(n^2)，空间O（1）
 * 验证算法正确，写一个对数器，产生足够多的数
 *
 * 写一个程序证明选择排序不稳定
 */
public class SelectionSort {
    public static void main(String[] args) {
        int arr[]={9,2,4,5,1,3,8,6};
        /**大O分析
         * 时间复杂度(n-1)+(n-2)+...+1=(n-1)n/2  忽略低次项O (n^2)
         * 空间复杂度o（1）变量不算，也没有新建数组重放
         */
        for(int i=0;i<arr.length;i++)
        {
            int minPos=i;
            for (int j = i+1; j < arr.length; j++) {
                minPos=arr[j]<arr[minPos]?j:minPos;
            }
            swap(arr,i,minPos);
        }
        print(arr);
    }
    static void swap(int[] arr,int i,int minPos)
    {
        int temp=arr[i];
        arr[i]=arr[minPos];
        arr[minPos]=temp;
    }
    static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }
    }
}

